package heap.medium;

import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * 将整数按权重排序
 * 示例 1：
 *
 * 输入：lo = 12, hi = 15, k = 2
 * 输出：13
 * 解释：12 的权重为 9（12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）
 * 13 的权重为 9
 * 14 的权重为 17
 * 15 的权重为 17
 * 区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ，答案是第二个整数也就是 13 。
 * 注意，12 和 13 有相同的权重，所以我们按照它们本身升序排序。14 和 15 同理。
 * 示例 2：
 *
 * 输入：lo = 1, hi = 1, k = 1
 * 输出：1
 * 示例 3：
 *
 * 输入：lo = 7, hi = 11, k = 4
 * 输出：7
 * 解释：区间内整数 [7, 8, 9, 10, 11] 对应的权重为 [16, 3, 19, 6, 14] 。
 * 按权重排序后得到的结果为 [8, 10, 11, 7, 9] 。
 * 排序后数组中第 4 个数字为 7 。
 * 示例 4：
 *
 * 输入：lo = 10, hi = 20, k = 5
 * 输出：13
 * 示例 5：
 *
 * 输入：lo = 1, hi = 1000, k = 777
 * 输出：570
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-integers-by-the-power-value
 */
public class SortIntegersByThePowerValue_1387 {


    public int getKth(int lo, int hi, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = lo; i <= hi; i++) {
            int x = i;
            int count = 0;
            while(x != 1) {
                if (x % 2 == 0)
                    x = x / 2;
                else
                    x = 3 * x + 1;
                count++;
            }
            map.put(i, count);
        }

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> {
            if (map.get(a).equals(map.get(b)))
                return b - a;
            else
                return map.get(b) - map.get(a);
        });

        for (Integer integer : map.keySet()) {
            maxHeap.offer(integer);
            if (k < maxHeap.size())
                maxHeap.poll();
        }

        return maxHeap.peek();
    }

    public int getKthArr(int lo, int hi, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> {
            if (a[1] == b[1])
                return b[0] - a[0];
            else
                return b[1] - a[1];
        });
        for (int i = lo; i <= hi; i++) {
            maxHeap.offer(new int[]{i, getP(i)});
            if (k < maxHeap.size())
                maxHeap.poll();
        }
        return maxHeap.peek()[0];
    }

    private int getP(int x) {
        int count = 0;
        while(x != 1) {
            if (x % 2 == 0)
                x = x / 2;
            else
                x = 3 * x + 1;
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        SortIntegersByThePowerValue_1387 sbt = new SortIntegersByThePowerValue_1387();
        System.out.println(sbt.getKth(12, 15, 2));
        System.out.println(sbt.getKth(1, 1, 1));
        System.out.println(sbt.getKth(7, 11, 4));
        System.out.println(sbt.getKthArr(12, 15, 2));
        System.out.println(sbt.getKthArr(1, 1, 1));
        System.out.println(sbt.getKthArr(7, 11, 4));
        System.out.println(sbt.getKthArr(1, 1000, 777));
    }
}
